{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Absolute Sum of Any Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAbsoluteSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #任意子数组和的绝对值的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。一个子数组 <code>[nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>]</code> 的 <strong>和的绝对值</strong> 为 <code>abs(nums<sub>l</sub> + nums<sub>l+1</sub> + ... + nums<sub>r-1</sub> + nums<sub>r</sub>)</code> 。</p>\n",
    "\n",
    "<p>请你找出 <code>nums</code> 中 <strong>和的绝对值</strong> 最大的任意子数组（<b>可能为空</b>），并返回该 <strong>最大值</strong> 。</p>\n",
    "\n",
    "<p><code>abs(x)</code> 定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>x</code> 是负整数，那么 <code>abs(x) = -x</code> 。</li>\n",
    "\t<li>如果 <code>x</code> 是非负整数，那么 <code>abs(x) = x</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,-3,2,3,-4]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,-5,1,-4,3,-2]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-absolute-sum-of-any-subarray](https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-absolute-sum-of-any-subarray](https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-3,2,3,-4]', '[2,-5,1,-4,3,-2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        posMax,negMin = 0,0\n",
    "        posSum,negSum = 0,0 \n",
    "\n",
    "        for n in nums:\n",
    "            posSum += n \n",
    "            posMax = max(posMax,posSum)\n",
    "            posSum = max(0,posSum)\n",
    "\n",
    "            negSum += n \n",
    "            negMin = min(negMin,negSum)\n",
    "            negSum = min(0,negSum)\n",
    "\n",
    "        return max(posMax,-negMin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans= f_max = f_min= 0\n",
    "        for x in nums:\n",
    "            f_max= max(f_max, 0) + x\n",
    "            f_min= min(f_min, 0) + x\n",
    "            ans=max(ans, f_max, -f_min)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans = f_max = f_min=0\n",
    "        for x in nums:\n",
    "            f_max = max(f_max, 0) + x\n",
    "            f_min = min(f_min, 0) + x\n",
    "            ans = max(ans, f_max, -f_min)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans = f_max = f_min=0\n",
    "        for x in nums:\n",
    "            f_max = max(f_max, 0) + x\n",
    "            f_min = min(f_min, 0) + x\n",
    "            ans = max(ans, f_max, -f_min)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = min_pre = max_pre = ret = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            ret = max(ret, pre - min_pre, max_pre - pre)\n",
    "            min_pre = min(min_pre, pre)\n",
    "            max_pre = max(max_pre, pre)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        min_pre = 0\n",
    "        max_pre = 0\n",
    "        pre_sum = 0\n",
    "        ans = -inf\n",
    "        ans1 = inf\n",
    "        for num in nums:\n",
    "            pre_sum += num\n",
    "            ans = max(ans,pre_sum-min_pre)\n",
    "            ans1 = min(ans1,pre_sum-max_pre)\n",
    "            min_pre = min(pre_sum,min_pre)\n",
    "            max_pre = max(max_pre,pre_sum)\n",
    "            \n",
    "        return max(abs(ans),abs(ans1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans = f_max = f_min = 0\n",
    "        for x in nums:\n",
    "            f_max = max(f_max, 0) + x\n",
    "            f_min = min(f_min, 0) + x\n",
    "            ans = max(f_max, ans, -f_min)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = min_pre = max_pre = ret = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            ret = max(ret, pre - min_pre, max_pre - pre)\n",
    "            min_pre = min(min_pre, pre)\n",
    "            max_pre = max(max_pre, pre)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        return max(pre) - min(pre)\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = min_pre = max_pre = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            min_pre = min(min_pre, pre)\n",
    "            max_pre = max(max_pre, pre)\n",
    "        return max_pre - min_pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 一维dp\n",
    "        pos_max, pos_sum = 0, 0\n",
    "        neg_min, neg_sum = 0, 0\n",
    "        for i in nums:\n",
    "            pos_sum += i\n",
    "            if pos_sum < 0:\n",
    "                pos_sum = 0\n",
    "            if pos_sum > pos_max:\n",
    "                pos_max = pos_sum\n",
    "            print(\"+\", i, pos_sum, pos_max)\n",
    "\n",
    "            neg_sum += i\n",
    "            if neg_sum > 0:\n",
    "                neg_sum = 0\n",
    "            if neg_sum < neg_min:\n",
    "                neg_min = neg_sum\n",
    "            print(\"-\", i, neg_sum, neg_min)\n",
    "        return max(pos_max, -neg_min)\n",
    "        # 二维dp 不好\n",
    "        \"\"\"\n",
    "        new_nums = []\n",
    "        temp_val = 0\n",
    "        # print(nums)\n",
    "        for i in nums:\n",
    "            if temp_val == 0 or temp_val > 0 and i > 0 or temp_val < 0 and i < 0:\n",
    "                temp_val += i\n",
    "            else:\n",
    "                new_nums.append(temp_val)\n",
    "                temp_val = i\n",
    "        if temp_val:\n",
    "            new_nums.append(temp_val)\n",
    "        # print(new_nums)\n",
    "        \n",
    "        dp = [new_nums[0]]\n",
    "        max_val = abs(dp[-1])\n",
    "        for i in new_nums[1:]:\n",
    "            dp.append(dp[-1] + i)\n",
    "            max_val = max(max_val, abs(dp[-1]))\n",
    "            # print(i, max_val)\n",
    "        # print(dp, max_val)\n",
    "        for i in range(1, len(new_nums)):\n",
    "            for j in range(i, len(new_nums)):\n",
    "                dp[j] -= new_nums[i-1]\n",
    "                # print(i, j, dp[j])\n",
    "                max_val = max(max_val, abs(dp[j]))\n",
    "        \n",
    "        return max_val\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        minn, maxx = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            maxx = max(maxx, 0) + nums[i]\n",
    "            minn = min(minn, 0) + nums[i]\n",
    "            ans = max(ans, maxx, -minn)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        sup, inf = -1,  1\n",
    "        pos_sum, neg_sum = 0, 0\n",
    "        for num in nums:\n",
    "            pos_sum += num\n",
    "            sup = max(sup, pos_sum)\n",
    "            pos_sum = max(0, pos_sum)\n",
    "\n",
    "            neg_sum += num\n",
    "            inf = min(inf, neg_sum)\n",
    "            neg_sum = min(0, neg_sum)\n",
    "            print(inf, neg_sum)\n",
    "\n",
    "        return max(sup, -inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        sup, inf = 0,  0\n",
    "        pos_sum, neg_sum = 0, 0\n",
    "        for num in nums:\n",
    "            pos_sum += num\n",
    "            sup = max(sup, pos_sum)\n",
    "            pos_sum = max(0, pos_sum)\n",
    "\n",
    "            neg_sum += num\n",
    "            inf = min(inf, neg_sum)\n",
    "            neg_sum = min(0, neg_sum)\n",
    "            print(inf, neg_sum)\n",
    "\n",
    "        return max(sup, -inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ans = f_max = f_min = 0\n",
    "        for x in nums:\n",
    "            f_max = max(f_max, 0) + x\n",
    "            f_min = min(f_min, 0) + x\n",
    "            ans = max(ans, f_max, -f_min)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        presum=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            presum[i]=presum[i-1]+nums[i-1]\n",
    "        return max(presum)-min(presum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        def f(nums, flag):\n",
    "            ans, tmp = 0, 0\n",
    "            for num in nums:\n",
    "                tmp += num\n",
    "                ans = max(tmp, ans) if flag else min(tmp, ans)\n",
    "                tmp = max(tmp, 0) if flag else min(tmp, 0)\n",
    "            return ans\n",
    "        return max(f(nums, True), -f(nums, False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return abs(nums[0])\n",
    "        ns = []\n",
    "        tmp = nums[0]\n",
    "        for i in nums[1:]:\n",
    "            if i * tmp >= 0:\n",
    "                tmp += i\n",
    "            else:\n",
    "                ns.append(tmp)\n",
    "                tmp = i\n",
    "        ns.append(tmp)\n",
    "        ans = f_max = f_min = 0\n",
    "        for x in ns:\n",
    "            f_max = max(f_max, 0) + x\n",
    "            f_min = min(f_min, 0) + x\n",
    "            ans = max(ans, f_max, -f_min)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 存最大值和最小值\n",
    "        min_val = inf\n",
    "        max_val = -inf\n",
    "        pre_val = 0\n",
    "        res = -inf\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0:\n",
    "                min_val = min(min_val, pre_val)\n",
    "                max_val = max(max_val, pre_val)\n",
    "            pre_val += nums[i]            \n",
    "            if i > 0:\n",
    "                max_cur = max(abs(pre_val - min_val),abs(pre_val - max_val))\n",
    "                res = max(res,max_cur,abs(pre_val))\n",
    "\n",
    "            print(i,pre_val,min_val,max_val,res)\n",
    "        return max(abs(nums[0]),res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        preSum = [0] * (len(nums) + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            preSum[i + 1] = preSum[i] + num\n",
    "        return max(preSum) - min(preSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre_sum=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre_sum[i]=pre_sum[i-1]+nums[i-1]\n",
    "        ans=0\n",
    "        return max(pre_sum)-min(pre_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i]=pre[i-1]+nums[i-1]\n",
    "        pre.sort()\n",
    "        return pre[n]-pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        return max(s) - min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i]=pre[i-1]+nums[i-1]\n",
    "        pre.sort()\n",
    "        return pre[n]-pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        dp = copy.deepcopy(nums)\n",
    "        ret = abs(nums[0])\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i], dp[i-1]+dp[i])\n",
    "            ret = max(ret, dp[i])\n",
    "        for i in range(1, n):\n",
    "            nums[i] = min(nums[i], nums[i-1]+nums[i])\n",
    "            ret = max(ret, -nums[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        summ=[0]\n",
    "        for i in nums:\n",
    "            summ.append(summ[-1]+i)\n",
    "        return abs(max(summ)-min(summ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = min_pre = max_pre = ret = 0\n",
    "        for x in nums:\n",
    "            pre += x\n",
    "            ret = max(ret, pre - min_pre, max_pre - pre)\n",
    "            min_pre = min(min_pre, pre)\n",
    "            max_pre = max(max_pre, pre)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        return max(pre) - min(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        res = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            res[i+1] = res[i] + nums[i]\n",
    "        return max(res) - min(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = [0]\n",
    "        for n in nums:\n",
    "            s.append(s[-1] + n)\n",
    "        return max(s) - min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        minVal = 0\n",
    "        maxVal = 0\n",
    "        results = 0\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1])\n",
    "            maxVal = max(maxVal, dp[i])\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        for j in range(1, len(nums) + 1):\n",
    "            dp[j] = min(dp[j - 1] + nums[j - 1], nums[j - 1])\n",
    "            minVal = min(minVal, dp[j])\n",
    "        results = max(maxVal, -minVal)\n",
    "        return results\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        ll = list(itertools.accumulate(nums, initial=0))\n",
    "        return max(ll) - min(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = [*accumulate(nums, initial=0)]\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        presum = list(itertools.accumulate(nums, initial=0))\n",
    "        return max(presum)-min(presum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = [0]\n",
    "        for n in nums:\n",
    "            s.append(s[-1] + n)\n",
    "        return max(s) - min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums\n",
    "        ans = 0\n",
    "        s = SortedList([0])\n",
    "        for i, x in enumerate(nums):\n",
    "            if i == 0: continue\n",
    "            ans = max(ans, abs(x))\n",
    "            nums[i] += nums[i - 1]\n",
    "            ans = max(ans, max(abs(nums[i] - s[0]), abs(nums[i] - s[-1])))\n",
    "            s.add(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        dp=[0]*len(nums)\n",
    "        cur=dp[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>0:\n",
    "                if cur<=0:\n",
    "                    cur=nums[i]\n",
    "                else:\n",
    "                    cur+=nums[i]\n",
    "                dp[i]=max(dp[i-1],cur)\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "                if cur>0:\n",
    "                    cur+=nums[i]\n",
    "                if cur<0:\n",
    "                    cur=0\n",
    "        dp1=[0]*len(nums)\n",
    "        cur=dp1[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<0:\n",
    "                if cur>=0:\n",
    "                    cur=nums[i]\n",
    "                else:\n",
    "                    cur+=nums[i]\n",
    "                dp1[i]=min(dp1[i-1],cur)\n",
    "            else:\n",
    "                dp1[i]=dp1[i-1]\n",
    "                if cur<0:\n",
    "                    cur+=nums[i]\n",
    "                if cur>0:\n",
    "                    cur=0\n",
    "        print(dp,dp1)\n",
    "        return max(abs(dp[len(nums)-1]),abs(dp1[len(nums)-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        map_list = [0]\n",
    "        res = pre_sum = 0\n",
    "        l = len(nums)\n",
    "        case1_max = 0\n",
    "        case1_maxxu = 0\n",
    "        \n",
    "        case2_min = 0\n",
    "        case2_minxu = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            pre_sum += nums[i]\n",
    "            map_list.append(pre_sum)\n",
    "            if pre_sum >= case1_max:\n",
    "                case1_max = map_list[i+1]\n",
    "                case1_maxxu = i+1\n",
    "            if pre_sum <= case2_min:\n",
    "                case2_min = map_list[i+1]\n",
    "                case2_minxu = i+1\n",
    "   \n",
    "#情况一：最大-（最大前面的）最小\n",
    "        test1 = map_list[0:case1_maxxu]\n",
    "        if test1:\n",
    "            case1_min = min(test1)\n",
    "        else:\n",
    "            case1_min = 0\n",
    "        case1_num = case1_max-case1_min\n",
    "\n",
    "#情况二：最小-（最小前面的）最大\n",
    "        test2 = map_list[0:case2_minxu]\n",
    "        if test2:\n",
    "            case2_max = max(test2)\n",
    "        else:\n",
    "            case2_max = 0\n",
    "        case2_num = abs(case2_min-case2_max)\n",
    "\n",
    "        res = max(case1_num,case2_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        #求一下最大连续子列和和最小连续子列和即可  经典dp\n",
    "        maxn=[]#注意这个是存的截至此处的最大子列和，最后答案不一定截至此处！因此要再取一下最大，注意，别想错！！！\n",
    "        minn=[]\n",
    "        nowmax=None\n",
    "        nowmin=None\n",
    "        n=len(nums)\n",
    "        for i in range(0,n):\n",
    "            if i==0:\n",
    "                maxn.append(nums[i])\n",
    "                minn.append(nums[i])#别忘了！要能看出来！\n",
    "            else:\n",
    "                maxn.append(max(maxn[i-1]+nums[i],nums[i]))\n",
    "                minn.append(min(minn[i-1]+nums[i],nums[i]))\n",
    "            if nowmax is None or maxn[i]>nowmax:\n",
    "                nowmax=maxn[i]\n",
    "            if nowmin is None or minn[i]<nowmin:#别忘改方向！\n",
    "                nowmin=minn[i]\n",
    "        return max(nowmax,abs(nowmin))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        map_list = [0]\n",
    "        res = pre_sum = 0\n",
    "        l = len(nums)\n",
    "        case1_max = 0\n",
    "        case1_maxxu = 0\n",
    "        \n",
    "        case2_min = 0\n",
    "        case2_minxu = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            pre_sum += nums[i]\n",
    "            map_list.append(pre_sum)\n",
    "            if pre_sum >= case1_max:\n",
    "                case1_max = map_list[i+1]\n",
    "                case1_maxxu = i+1\n",
    "            if pre_sum <= case2_min:\n",
    "                case2_min = map_list[i+1]\n",
    "                case2_minxu = i+1\n",
    "   \n",
    "#情况一：最大-（最大前面的）最小\n",
    "        test1 = map_list[0:case1_maxxu]\n",
    "        if test1:\n",
    "            case1_min = min(test1)\n",
    "        else:\n",
    "            case1_min = 0\n",
    "        case1_num = case1_max-case1_min\n",
    "\n",
    "#情况二：最小-（最小前面的）最大\n",
    "        test2 = map_list[0:case2_minxu]\n",
    "        if test2:\n",
    "            case2_max = max(test2)\n",
    "        else:\n",
    "            case2_max = 0\n",
    "        case2_num = abs(case2_min-case2_max)\n",
    "\n",
    "        res = max(case1_num,case2_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # dp = [0]*len(nums)\n",
    "        # dp[0] = abs(nums[0])\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     dp\n",
    "        res = abs(nums[0])\n",
    "        qianzui = [0]*len(nums)\n",
    "        qianzui[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            qianzui[i] = qianzui[i-1] + nums[i]\n",
    "            res = max(res,abs(qianzui[i]))\n",
    "        min_num = nums[0]\n",
    "        max_num = nums[0]\n",
    "        print(qianzui)\n",
    "        for right in range(len(nums)):\n",
    "            res = max(res,abs(qianzui[right]-max_num),abs(qianzui[right]-min_num))\n",
    "            min_num = min(qianzui[right],min_num)\n",
    "            max_num = max(qianzui[right],max_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        map_list = [0]\n",
    "        rec = pre_sum = 0\n",
    "        l = len(nums)\n",
    "        case1_max = 0\n",
    "        case1_maxxu = 0\n",
    "        case2_min = 0\n",
    "        case2_minxu = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            pre_sum += nums[i]\n",
    "            map_list.append(pre_sum)\n",
    "            if map_list[i+1] >= case1_max:\n",
    "                case1_max = map_list[i+1]\n",
    "                case1_maxxu = i+1\n",
    "            if map_list[i+1] <= case2_min:\n",
    "                case2_min = map_list[i+1]\n",
    "                case2_minxu = i+1\n",
    "\n",
    "        test1 = map_list[0:case1_maxxu]\n",
    "        test1.sort()\n",
    "        if test1:\n",
    "            case1_min = test1[0]\n",
    "        else:\n",
    "            case1_min = 0\n",
    "        case1_num = case1_max-case1_min\n",
    "\n",
    "        test2 = map_list[0:case2_minxu]\n",
    "        test2.sort(reverse = True)\n",
    "        if test2:\n",
    "            case2_max = test2[0]\n",
    "        else:\n",
    "            case2_max = 0\n",
    "        case2_num = abs(case2_min-case2_max)\n",
    "\n",
    "        res = max(case1_num,case2_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        presum = list(accumulate(nums,initial = 0))\n",
    "        print(presum)\n",
    "        return max(presum) - min(presum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre_sum = [nums[0]]\n",
    "        for i in range(len(nums)-1):\n",
    "            cur = nums[i+1]\n",
    "            pre_sum.append(pre_sum[i]+cur)\n",
    "        \n",
    "        print(pre_sum)\n",
    "        # res = abs(pre_sum[0])\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     cur_sum = pre_sum[i]\n",
    "        #     res = max(res, abs(cur_sum))\n",
    "        #     for j in range(0, i):\n",
    "        #         cur_diff = cur_sum - pre_sum[j]\n",
    "        #         res = max(res, abs(cur_diff))\n",
    "        max_sum = max(pre_sum)\n",
    "        min_sum = min(pre_sum)\n",
    "        diff = max_sum - min_sum\n",
    "\n",
    "\n",
    "        return max(abs(max_sum), abs(min_sum), abs(diff))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        map_list = [0]\n",
    "        res = pre_sum = 0\n",
    "        l = len(nums)\n",
    "        case1_max = 0\n",
    "        case1_maxxu = 0\n",
    "        \n",
    "        case2_min = 0\n",
    "        case2_minxu = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            pre_sum += nums[i]\n",
    "            map_list.append(pre_sum)\n",
    "            if pre_sum >= case1_max:\n",
    "                case1_max = map_list[i+1]\n",
    "                case1_maxxu = i+1\n",
    "            if pre_sum <= case2_min:\n",
    "                case2_min = map_list[i+1]\n",
    "                case2_minxu = i+1\n",
    "        \n",
    "#情况一：最大-（最大前面的）最小\n",
    "        test1 = map_list[0:case1_maxxu]\n",
    "        test1.sort()\n",
    "        if test1:\n",
    "            case1_min = test1[0]\n",
    "        else:\n",
    "            case1_min = 0\n",
    "        case1_num = case1_max-case1_min\n",
    "\n",
    "#情况二：最小-（最小前面的）最大\n",
    "        test2 = map_list[0:case2_minxu]\n",
    "        test2.sort(reverse = True)\n",
    "        if test2:\n",
    "            case2_max = test2[0]\n",
    "        else:\n",
    "            case2_max = 0\n",
    "        case2_num = abs(case2_min-case2_max)\n",
    "\n",
    "        res = max(case1_num,case2_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 前缀和 + 暴力\n",
    "        n = len(nums)\n",
    "        s = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + nums[i]\n",
    "        print(s)\n",
    "        ma = 0\n",
    "        # for l in range(n):\n",
    "        #    for r in range(l,n):\n",
    "        #        ma = max(ma,abs(s[r+1]-s[l]))\n",
    "        return max(s) - min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # dp = [0]*len(nums)\n",
    "        # dp[0] = abs(nums[0])\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     dp\n",
    "        res = abs(nums[0])\n",
    "        qianzui = [0]*len(nums)\n",
    "        qianzui[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            qianzui[i] = qianzui[i-1] + nums[i]\n",
    "            res = max(res,abs(qianzui[i]))\n",
    "        min_num = nums[0]\n",
    "        max_num = nums[0]\n",
    "        print(qianzui)\n",
    "        for right in range(len(nums)):\n",
    "            res = max(res,abs(qianzui[right]-max_num),abs(qianzui[right]-min_num))\n",
    "            min_num = min(qianzui[right],min_num)\n",
    "            max_num = max(qianzui[right],max_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        #求一下最大连续子列和和最小连续子列和即可  经典dp\n",
    "        maxn=[nums[0]]#注意这个是存的截至此处的最大子列和，最后答案不一定截至此处！因此要再取一下最大，注意，别想错！！！\n",
    "        minn=[nums[0]]\n",
    "        nowmax=nums[0]\n",
    "        nowmin=nums[0]\n",
    "        n=len(nums)\n",
    "        for i in range(1,n):\n",
    "            t=nums[i]\n",
    "            maxn.append(max(maxn[i-1]+t,t))\n",
    "            minn.append(min(minn[i-1]+t,t))\n",
    "            if maxn[i]>nowmax:\n",
    "                nowmax=maxn[i]\n",
    "            if minn[i]<nowmin:#别忘改方向！\n",
    "                nowmin=minn[i]\n",
    "        return max(nowmax,abs(nowmin))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        preSum = [0] + list(accumulate(nums))\n",
    "        print(preSum)\n",
    "        return max(preSum) - min(preSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        pre_sum = list(itertools.accumulate(nums))\n",
    "        pre_sum = [0] + pre_sum\n",
    "        print(pre_sum)\n",
    "        return max(pre_sum) - min(pre_sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        sum_nums = [0] * N\n",
    "        dp_min = [0] + [nums[0]] * N\n",
    "        dp_max = [0] + [nums[0]] * N \n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if i == 0:\n",
    "                sum_nums[i] = nums[0]\n",
    "            else:\n",
    "                sum_nums[i] = sum_nums[i-1] + nums[i]\n",
    "                dp_min[i+1] = min(dp_min[i], sum_nums[i])\n",
    "                dp_max[i+1] = max(dp_max[i], sum_nums[i])\n",
    "            res = max(res, abs(sum_nums[i] - dp_min[i]), abs(sum_nums[i] - dp_max[i]))\n",
    "        res = max(res, abs(dp_min[N]), abs(dp_max[N]))\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial = 0))\n",
    "        print(s)\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        #\"时间复杂度过高不能通过\"\n",
    "        # n = len(nums)\n",
    "        # index = 0\n",
    "        # for i in range(n):\n",
    "        #     flag = nums[i]\n",
    "        #     jump = 0\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if abs(flag + nums[j]+jump) > abs(flag):\n",
    "        #             flag = flag + nums[j] + jump\n",
    "        #             #print(\"#\",i,j)\n",
    "        #             #print(flag)\n",
    "        #             jump = 0\n",
    "        #         else :\n",
    "        #             jump = nums[j] + jump\n",
    "        #     if (abs(flag) > abs(index) ):\n",
    "        #         index = flag\n",
    "        # return abs(index) \n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        print(s)\n",
    "        return max(s) - min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        print(s)\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1749 lang=python\n",
    "#\n",
    "# [1749] 任意子数组和的绝对值的最大值\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def maxAbsoluteSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pre = [0]\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            pre.append(sum)\n",
    "        print(pre)\n",
    "        return max(pre) - min(pre)\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        print(s)\n",
    "        return max(s) - min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(2)]\n",
    "        dp[0][0] = dp[1][0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = nums[i] + min(dp[0][i-1], 0)\n",
    "            dp[1][i] = nums[i] + max(dp[1][i-1], 0)\n",
    "        return max(max(dp[1]), -min(dp[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0]*n\n",
    "        dp1 = [0]*n\n",
    "        dp0[0] = nums[0]\n",
    "        dp1[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp0[i] = max(dp0[i-1]+nums[i],nums[i])  \n",
    "            dp1[i] = min(dp1[i-1]+nums[i],nums[i])\n",
    "        maxsum = max(dp0)\n",
    "        minsum = min(dp1)\n",
    "        return max(maxsum,-minsum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp1=[0]*(n+1)\n",
    "        dp2=[0]*(n+1)\n",
    "        dp1[0]=max(nums[0],0)\n",
    "        dp2[0]=min(0,nums[0])\n",
    "        c=max(abs(dp1[0]),abs(dp2[0]))\n",
    "        if n>1:\n",
    "            for i in range(1,n):\n",
    "                dp1[i]=max(dp1[i-1],0)+nums[i]\n",
    "                dp2[i]=min(dp2[i-1],0)+nums[i]\n",
    "                c=max(c,abs(dp1[i]),abs(dp2[i]))\n",
    "        return c\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        #感觉有点像前缀和的变式,可是求出前缀和也要O(n^2)的时间复杂度，还是会超时，麻痹的，我特么参考题解，感觉自己就是傻逼，直接 max(preSum)-min(preSum)\n",
    "        # n=len(nums)\n",
    "        # preSum=[0]*(n+1)\n",
    "        # for i in range(1,n+1):\n",
    "        #     preSum[i]=preSum[i-1]+nums[i-1]\n",
    "        \n",
    "        # return max(preSum)-min(preSum)\n",
    "\n",
    "        #参考题解，dp[i]表示以nums[i]结尾的子数组绝对值和的最大值\n",
    "        # 但请注意，有可能是正数一直累加，也有可能是负数一直累加负数\n",
    "        n=len(nums)\n",
    "        dp0=[0]*n\n",
    "        dp1=[0]*n\n",
    "        dp0[0]=nums[0]\n",
    "        dp1[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp0[i]=max(dp0[i-1]+nums[i],nums[i])\n",
    "            dp1[i]=min(dp1[i-1]+nums[i],nums[i])\n",
    "        return max(abs(min(dp1)),max(dp0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        dp_max,dp_min=[0]*len(nums),[0]*len(nums)\n",
    "        dp_max[0]=nums[0]\n",
    "        dp_min[0]=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp_max[i]=max(dp_max[i-1]+nums[i],nums[i])\n",
    "            dp_min[i]=min(dp_min[i-1]+nums[i],nums[i])\n",
    "\n",
    "        return max(max(dp_max),-min(dp_min))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # ans = f_max = f_min=0\n",
    "        # for x in nums:\n",
    "        #     f_max = max(f_max, 0) + x\n",
    "        #     f_min = min(f_min, 0) + x\n",
    "        #     ans = max(ans, f_max, -f_min)\n",
    "        # return ans\n",
    "        if len(nums) == 1:\n",
    "            return abs(nums[0])\n",
    "        if len(nums) == 2:\n",
    "            return max(abs(nums[0]), abs(nums[1]),abs(nums[0]+nums[1]))\n",
    "        f = [float(\"-inf\")] * len(nums)\n",
    "        g = [float(\"inf\")] *len(nums)\n",
    "        f[0] = nums[0]\n",
    "        g[0] = nums[0]\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            f[i] = max(f[i-1], 0) + nums[i]\n",
    "            g[i] = min(g[i-1], 0) + nums[i]\n",
    "            ans = max(f[i], abs(g[i]), ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp1=[0]*(n+1)\n",
    "        dp2=[0]*(n+1)\n",
    "        dp1[0]=max(nums[0],0)\n",
    "        dp2[0]=min(0,nums[0])\n",
    "        c=max(abs(dp1[0]),abs(dp2[0]))\n",
    "        if n>1:\n",
    "            for i in range(1,n):\n",
    "                dp1[i]=max(dp1[i-1],0)+nums[i]\n",
    "                dp2[i]=min(dp2[i-1],0)+nums[i]\n",
    "                c=max(c,abs(dp1[i]),abs(dp2[i]))\n",
    "        return c\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return abs(nums[0])\n",
    "        dpmax = [0 for i in nums]\n",
    "        dpmin = [0 for i in nums]\n",
    "        dpmax[0] = dpmin[0] = nums[0]\n",
    "        res = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dpmax[i] = max(nums[i], nums[i] + dpmax[i - 1])\n",
    "            dpmin[i] = min(nums[i], nums[i] + dpmin[i - 1])\n",
    "            res = max(res, max(abs(dpmax[i]), abs(dpmin[i])))\n",
    "        return res            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return abs(nums[0])\n",
    "        dpmax = [0 for i in nums]\n",
    "        dpmin = [0 for i in nums]\n",
    "        dpmax[0] = dpmin[0] = nums[0]\n",
    "        res = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dpmax[i] = max(nums[i], nums[i] + dpmax[i - 1])\n",
    "            dpmin[i] = min(nums[i], nums[i] + dpmin[i - 1])\n",
    "            res = max(res, max(abs(dpmax[i]), abs(dpmin[i])))\n",
    "        return res            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        dpmax=[0 for i in range(len(nums))]\n",
    "        dpmax[0]=nums[0]\n",
    "        dpmin=[0 for i in range(len(nums))]\n",
    "        dpmin[0]=nums[0]\n",
    "        re=abs(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            dpmax[i]=max(nums[i],dpmax[i-1]+nums[i],dpmin[i-1]+nums[i])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            dpmin[i]=min(nums[i],dpmax[i-1]+nums[i],dpmin[i-1]+nums[i])\n",
    "              \n",
    "            re=max(abs(dpmin[i]),abs(dpmax[i]),re)\n",
    "\n",
    "\n",
    "\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # if len(nums)==1:\n",
    "        #     return abs(nums[0])\n",
    "        # res = 0\n",
    "        # dp = [0 for i in range(len(nums))]\n",
    "        # dp[0] = nums[0]\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     if nums[i]>=0:\n",
    "        #         if dp[i-1]>=0:\n",
    "        #             dp[i] = dp[i-1]+nums[i]\n",
    "        #         else:\n",
    "        #             if abs(dp[i-1]+nums[i])>=nums[i]:\n",
    "        #                 dp[i] =  dp[i-1]+nums[i]\n",
    "        #             else:\n",
    "        #                 dp[i] = nums[i]\n",
    "        #     else:\n",
    "        #         if dp[i-1]<=0:\n",
    "        #             dp[i] = dp[i-1]+nums[i]\n",
    "        #         else:\n",
    "        #             if abs(dp[i-1]+nums[i])>=abs(nums[i]):\n",
    "        #                 dp[i] = dp[i-1]+nums[i]\n",
    "        #             else:\n",
    "        #                 dp[i] = nums[i]\n",
    "        #     # res = max(res,abs(dp[i]))\n",
    "        # for k in dp:\n",
    "        #     res = max(res,abs(k))\n",
    "        # return max(res,abs(sum(nums)))\n",
    "        if len(nums)==1:\n",
    "            return abs(nums[0])\n",
    "        dp_low = [0 for i in range(len(nums))]\n",
    "        dp_upp = [0 for i in range(len(nums))]\n",
    "        dp_low[0] = nums[0]\n",
    "        dp_upp[0] = nums[0]\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            dp_low[i] = min(dp_low[i-1]+nums[i],nums[i])\n",
    "            dp_upp[i] = max(dp_upp[i-1]+nums[i],nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            res = max(max(abs(dp_low[i]),abs(dp_upp[i])),res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # if len(nums)==1:\n",
    "        #     return abs(nums[0])\n",
    "        # res = 0\n",
    "        # dp = [0 for i in range(len(nums))]\n",
    "        # dp[0] = nums[0]\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     if nums[i]>=0:\n",
    "        #         if dp[i-1]>=0:\n",
    "        #             dp[i] = dp[i-1]+nums[i]\n",
    "        #         else:\n",
    "        #             if abs(dp[i-1]+nums[i])>=nums[i]:\n",
    "        #                 dp[i] =  dp[i-1]+nums[i]\n",
    "        #             else:\n",
    "        #                 dp[i] = nums[i]\n",
    "        #     else:\n",
    "        #         if dp[i-1]<=0:\n",
    "        #             dp[i] = dp[i-1]+nums[i]\n",
    "        #         else:\n",
    "        #             if abs(dp[i-1]+nums[i])>=abs(nums[i]):\n",
    "        #                 dp[i] = dp[i-1]+nums[i]\n",
    "        #             else:\n",
    "        #                 dp[i] = nums[i]\n",
    "        #     # res = max(res,abs(dp[i]))\n",
    "        # for k in dp:\n",
    "        #     res = max(res,abs(k))\n",
    "        # return max(res,abs(sum(nums)))\n",
    "        if len(nums)==1:\n",
    "            return abs(nums[0])\n",
    "        dp_low = [0 for i in range(len(nums))]\n",
    "        dp_upp = [0 for i in range(len(nums))]\n",
    "        dp_low[0] = nums[0]\n",
    "        dp_upp[0] = nums[0]\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            dp_low[i] = min(dp_low[i-1]+nums[i],nums[i])\n",
    "            dp_upp[i] = max(dp_upp[i-1]+nums[i],nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            res = max(max(abs(dp_low[i]),abs(dp_upp[i])),res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 前缀和即可\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        # 这里不用n方了！\n",
    "        pre_sum = list(accumulate(nums, initial=0))\n",
    "        return max(pre_sum) - min(pre_sum)\n",
    "\n",
    "        # 暴力n三方肯定超时\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = max(ans, abs(sum(nums[i: j])))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 维护两个，一个最大值，一个最小值，贪心算法\n",
    "        maxValue = [-float('inf')] * (len(nums) + 1)\n",
    "        minValue = [float('inf')] * (len(nums) + 1)\n",
    "\n",
    "        # maxValue = -float('inf')\n",
    "        # minValue = float('inf')\n",
    "\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            maxValue[i] = max(nums[i - 1], maxValue[i - 1] + nums[i - 1])\n",
    "            minValue[i] = min(nums[i - 1], minValue[i - 1] + nums[i - 1])\n",
    "        \n",
    "        absMax = abs(max(maxValue[1:]))\n",
    "        absMin = abs(min(minValue[1:]))\n",
    "\n",
    "        if absMin > absMax:\n",
    "            return absMin\n",
    "        return absMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # dp[i]表示以nums[i]为结尾的数组和\n",
    "        n=len(nums)\n",
    "        dp_max=[0]*n\n",
    "        dp_min=[0]*n\n",
    "        dp_max[0]=dp_min[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp_max[i]=max(nums[i],dp_max[i-1]+nums[i])\n",
    "            dp_min[i]=min(nums[i],dp_min[i-1]+nums[i])\n",
    "        return max(max(dp_max),-min(dp_min))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 最大值和最小值\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxSum = [0] * n\n",
    "        minSum = [0] * n\n",
    "        maxSum[0] = nums[0]\n",
    "        minSum[0] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            maxSum[i] = max(maxSum[i-1]+nums[i], nums[i])\n",
    "            minSum[i] = min(minSum[i-1]+nums[i], nums[i])\n",
    "        return max(abs(max(maxSum)), abs(min(minSum)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        dpp = [0] + nums[:]\n",
    "        dpn = [0] + nums[:]\n",
    "        for i in range(len(nums)):\n",
    "            dpp[i + 1] = dpp[i] + dpp[i + 1] if dpp[i] >= 0 else dpp[i + 1]\n",
    "            dpn[i + 1] = dpn[i] + dpn[i + 1] if dpn[i] <= 0 else dpn[i + 1]\n",
    "        return max(max(dpp),-min(dpn))\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        L1 = [0 for i in range(len(nums))]\n",
    "        L2 = [0 for i in range(len(nums))]\n",
    "        L1[0] = 0 if nums[0]<=0 else nums[0]\n",
    "        L2[0] = 0 if nums[0]>=0 else nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if(nums[i]==0):\n",
    "                L1[i], L2[i] = L1[i-1], L2[i-1]\n",
    "            elif(nums[i]>0):\n",
    "                L1[i] = L1[i-1] + nums[i]\n",
    "                L2[i] = 0 if L2[i-1]+nums[i]>=0 else L2[i-1]+nums[i]\n",
    "            else:\n",
    "                L2[i] = L2[i-1] + nums[i]\n",
    "                L1[i] = 0 if L1[i-1]+nums[i]<=0 else L1[i-1]+nums[i]\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            result = max(max(L1[i], -L2[i]), result)\n",
    "        return result\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 定义dp_max dp_min dp[i] 是以i开始到结尾的最大和或最小和 dp[i+1] = dp[i] - nums[i] \n",
    "\n",
    "       \n",
    "        dp_max = [0]  * len(nums)\n",
    "        dp_min = [0]  * len(nums)\n",
    "        max_0 = nums[0]\n",
    "        min_0 = nums[0]\n",
    "        total = 0\n",
    "        for n in nums:\n",
    "            total += n\n",
    "            max_0 = max(max_0, total)\n",
    "            min_0 = min(min_0, total)\n",
    "\n",
    "        dp_max[0] = max_0\n",
    "        dp_min[0] = min_0\n",
    "\n",
    "        for i, n in enumerate(nums[:-1]):\n",
    "            dp_max[i + 1] = dp_max[i] - n\n",
    "            dp_min[i + 1] = dp_min[i] - n\n",
    "        max_total = max(dp_max)\n",
    "        min_total = min(dp_min)\n",
    "        return max(abs(max_total), abs(min_total))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        f_n_1_max = nums[0]\n",
    "        f_n_1_min = nums[0]\n",
    "        m1,m2 = [f_n_1_max],[f_n_1_min]\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            f_max = max(f_n_1_max + nums[i],nums[i])\n",
    "            f_min = min(f_n_1_min + nums[i],nums[i])\n",
    "            m1.append(f_max)\n",
    "            m2.append(f_min)\n",
    "            f_n_1_max,f_n_1_min = f_max,f_min\n",
    "\n",
    "        return max(max(m1),abs(min(m2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        # 1 -3 2 3 -4\n",
    "        # 1 -2 2 5  1\n",
    "        # 1 -3 -1 2 -4\n",
    "        maxdp=[nums[0]]\n",
    "        mindp=[nums[0]]\n",
    "        res=max(abs(maxdp[-1]),abs(mindp[-1]))\n",
    "        for i in range(1,len(nums)):\n",
    "            maxdp.append(max(maxdp[-1]+nums[i],nums[i]))\n",
    "            mindp.append(min(mindp[-1]+nums[i],nums[i]))\n",
    "            res=max(abs(maxdp[-1]),abs(mindp[-1]),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*len(nums)\n",
    "        # dp2 = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if dp[i-1] > 0:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "        _max1 = max([abs(i) for i in dp])\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if dp[i-1] < 0:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "        _max2 = max([abs(i) for i in dp])\n",
    "\n",
    "        return max(_max1,_max2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        max_val = [nums[0]]\n",
    "        min_val = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            max_val.append(max(max_val[i - 1] + nums[i], nums[i]))\n",
    "            min_val.append(min(min_val[i - 1] + nums[i], nums[i]))\n",
    "        max_abs = -99999\n",
    "        for i in range(0, len(max_val)):\n",
    "            max_abs = max(max_abs, abs(max_val[i]), abs(min_val[i]))\n",
    "        return max_abs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsoluteSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxArr = [0 for x in range(len(nums)+1)]\n",
    "        minArr = [0 for x in range(len(nums)+1)]\n",
    "        for i in range(n):\n",
    "            maxArr[i+1] = max(nums[i], maxArr[i]+nums[i])\n",
    "            minArr[i+1] = min(nums[i], minArr[i]+nums[i])\n",
    "        maxSum = max(maxArr)\n",
    "        minSum = abs(min(minArr))\n",
    "        return maxSum if maxSum > minSum else minSum"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
